МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ ТЕРНОПІЛЬСЬКИЙ НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ імені Івана Пулюя Кафедра комп’ютерних наук ЛАБОРАТОРНА РОБОТА з предмету Теорія алгоритмів та математичні основи представлення знань Тема: Перетворення структури обчислювальних алгоритмів Тернопіль-2010 Лабораторна робота №4 Тема роботи: Перетворення структури обчислювальних алгоритмів. Мета роботи: Вивчення методів перетворення структури обчислювальних алгоритмів на прикладі алгоритмів фільтрації сигналів. Теоретичні відомості При практичній реадізації обчислювальних алгоритмів на ЕОМ загального призначення та спеціалізованих ЕОМ суттєвими є не тільки функція, яку реалізує алгоритм, але і його структура. Від структури алгоритму залежать швидкість виконання алгоритму, необхідний обєм пам`яті ЕОМ, необхідна кількість арифметично-логічних пристроїв (суматорів, помножувачів) при реалізації алгоритму у спеціалізованих ЕОМ, стійкість роботи алгоритму до похибок обчислень з скінченою точністю. Через це важливим є вивчення властивостей різних форм структури обчислювальних алгоритмів та методів переходу від однієї форми до іншої. Найбільш поширеними є пряма і канонічна форми структури алгоритмів. Пряма (основна) форма Канонічна форма Інші форми будуються в залежності від вимог до конкретної реалізації алгоритму. Перехід між різними формами можна здійснити проведенням тотожніх перетворень над різницевим рівнінням алгоритму або над передаточною функцією, яку отримують в результаті дискретного перетворення Фур`є або Z-перетворення різницевого рівняння. Проілюструвати проведення перетворення стрктури можна на прикладі рекурсивного алгоритму другого порядку. Різницеве рівняння алгоритму:
(1) Такий запис відповідає спруктурній схемі алгоритму у прямій формі (рис.1.а). Перехід від прямої форми до канонічної легко здійснити перетворенням передаточної функції. Z-перетворення різницевого рівняння:
Або
Передаточна функція:
Чисельник передаточної функції реалізує пряму (нерекурсивну) частину алгоритму, а знаменник – рекурсивну частину алгоритму. Передаточну функцію можна записати у вигляді:
, де
Така форма запису передаточної функції відповідає послідовному (каскадному) з’єднанню рекурсивної і нерекурсивної частин обчислювального алгоритму. Сумістивши затримки рекурсивної і нерекурсивної частин алгоритму отримаєм настутну структурну схему алгоритму (Рис.2.). У випадку, коли алгоритм заданий у вигляді структурної або граф-схеми або з допомогою системи рівнянь, зручно попередньо записати передаточну функцію а потім проводити перетворення над нею. Для того щоб звести опис алгоритму від структурної або граф схеми до передаточної функції необхідно: записати систему рівнянь для усіх внутрішніх і вихідних вузлцв схеми; виключенням змінних для внутрішніх вузлів звести систему рівнянь до одного рівняння виду у=H*x; функція H(z) , буде передаточною функцією алгоритму. Завдання до лабораторної роботи. Для алгоритму, який описується заданою системою рівнянь 7 
звести до каноннічної форми   Записати різницеве рівняння і передаточну функцію. Перейти до канонічної форми структури алгоритму. Побудувути структурну та граф-схеми алгоритму; Скласти програму реалізації такого алгоритму на ЕОМ у якій: а. операції множення та сумування реалізувати у вигляді окремих підпрограм; b. на вхід алгоритму подати послідовність з 20 відліків синусоїди; с. забезпечипи підрахунок кількості викликів підпрограм множення та додавання. Різницеве рівняння у канонічній формі: x4i=12,3x1i+4x1i–1 + 132x4i–1 – 46x4i–2 Передаточна функція у канонічній формі:
 Результат роботи. Рис.1 Структурна схема алгоритму
 Рис.2 Графсхема алгоритму  Блок-схема програми Текст програми unit Unit1; interface uses Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms, Dialogs, StdCtrls, ComCtrls, ExtCtrls, TeeProcs, TeEngine, Chart, Series; type TForm1 = class(TForm) Button1: TButton; Chart1: TChart; Series1: TFastLineS...